#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data; 
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

void PrevOrder(BTNode* root)
{
	if(root==NULL)
	{
		printf("N");
		return;
	}
	printf("%d",root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}


void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return;
	}
	InOrder(root->left);
	printf("%d", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d", root->data);

}
int BTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + BTreeSize(root->left) + BTreeSize(root->right);
}


int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return  BTreeLeafSize(root->left) + BTreeLeafSize(root->right);

}

int BTreeLeveKSize(BTNode* root,int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;

	return  BTreeLeveKSize(root->left,k-1) + BTreeLeveKSize(root->right,k-1);

}

int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	printf("%d\n", BTreeSize(root));
	printf("%d\n", BTreeLeafSize(root));
	printf("%d\n", BTreeLeveKSize(root,3));
	printf("%d\n", BTreeLeveKSize(root, 4));

	return 0;
}






